package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 1156. 单字符重复子串的最大长度   https://leetcode.cn/problems/swap-for-longest-repeated-character-substring
 */
public class LeetCode1156 {
    // 1、暴力解（超时）
    public static int maxRepOpt0(String text) {
        int n = text.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                String s = exchangeString(text, i, j);
                int length = getMaxStringLength(s);
                ans = Math.max(ans, length);
            }
        }
        return ans;
    }

    public static String exchangeString(String str, int i, int j) {
        char c = str.charAt(i);
        char c1 = str.charAt(j);
        StringBuilder sb = new StringBuilder(str);
        sb.replace(i, i + 1, c1 + "");
        sb.replace(j, j + 1, c + "");
        return sb.toString();
    }

    public static int getMaxStringLength(String str) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int temp = 1;
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] == chars[j]) {
                    temp++;
                } else {
                    break;
                }
            }
            ans = Math.max(ans, temp);
        }
        return ans;
    }

    // 2、滑动窗口
    public static int maxRepOpt1(String text) {
        Map<Character, Integer> count = new HashMap<>();
        for (int i = 0; i < text.length(); i++) {
            count.put(text.charAt(i), count.getOrDefault(text.charAt(i), 0) + 1);
        }
        int ans = 0;
        for (int i = 0; i < text.length(); ) {
            int j = i + 1;
            while (j < text.length() && text.charAt(i) == text.charAt(j)) {
                j++;
            }
            if (j - i < count.get(text.charAt(i)) && (i - 1 >= 0 || j < text.length())) {
                ans = Math.max(ans, j - i + 1);
            }

            int k = j + 1;
            while (k < text.length() && text.charAt(i) == text.charAt(k)) {
                k++;
            }
            ans = Math.max(ans, Math.min(k - i, count.get(text.charAt(i))));
            i = j;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(maxRepOpt1("ababa"));
        System.out.println(maxRepOpt1("aaabaaa"));
        System.out.println(maxRepOpt1("aaabbaaa"));
        System.out.println(maxRepOpt1("aaaaa"));
        System.out.println(maxRepOpt1("abcdef"));
        // 18
        System.out.println(maxRepOpt1("aabbbbbbbbbbabbbaabaaaaaaabababaaaaaababaaababbabbbabbbbaabbbbaabaaaaabaabbababbbaaaaaaabbbbaabbbaabaaaabaaabababaaababbbaaababaaaababbabbaabbaabbabbbabbbaabaabbabaaaaabbbbabaaabbaaabbaabbabbaabbbbaabaaababbbbaabaaaabbbaababaaaabaaaababaababbabaaaabaabaaababababaabbbbbbabbabbbabaabbabbbabaaabaabaaaabaaabbbbbbbbbaaabbababaaaabaaabbaaabbabbbaaababababbbbbbbbbbbabbbbbbaabbbaaababbaabaabbbababbaaaababaabababbbbbbababbabbaabbabababaababbbbaaaaabababbaabbaabaaabbaababaaabbbaaaabaaababbbbabbabbabaababbbabbbbbbbbaaaaabbbabbaaababaabbbbabbbabaabbabbbbaaabbbaabbaaaaaaabbbbbabaabbbaabbbaaaaabbbabaaaaabbabbabbabbaabaaaaabaabbbaaaababaaabbaabbbaabba"));
    }

}
